长大后想做什么？做回小孩！

0%

[LeetCode]——文本左右对齐

发表于 分类于 Valine：
本文字数： 537

又是一道很恶心的题，本身没有什么难以理解的算法或结构，全是细节堆积出来的。

NO.68 文本左右对齐 困难

8tq18P.png

8tqM4I.png

思路一：顺着思路模拟 直接贴一个discuss，看一下思路：

首先要理顺题意，给定一堆单词，让你放在固定长度字符串里

  1. 两个单词之间至少有一个空格，如果单词加空格长度超过maxWidth，说明该单词放不下，比如示例1:当我们保证this is an再加入example变成this is an example总长度超过maxWidth，所以这一行只能放下this is an 这三个单词;

  2. this is an长度小于maxWidth，我们考虑分配空格，并保证左边空格数大于右边的

  3. 最后一行，要尽量靠左，例如示例2的:”shall be “
    我们针对上面三个问题，有如下解决方案.

  4. 先找到一行最多可以容下几个单词;

  5. 分配空格，例如this is an，对于宽度为maxWidth，我们可以用maxWidth - all_word_len与需要空格数商为 单词间 空格至少的个数，余数是一个一个分配给左边.就能保证左边空格数大于右边的.例如16 - 8 = 8，a = 8 / 2， b = 8 % 2两个单词间要有4个空格，因为余数为零不用分配;

  6. 针对最后一行单独考虑;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> res = new ArrayList<>();
    int i = 0;
    int n = words.length;
    while (i < n) {
        // 找到一行可以容下单词
        int left = i;
        // 至少一行能放下一个单词
        int cur_row_len = words[i].length();
        i++;

        while (i < n) {
            if (cur_row_len + words[i].length() + 1 > maxWidth) break;
            ;
            cur_row_len += words[i].length() + 1;
            i++;
        }
        StringBuilder tmp = new StringBuilder();
        // 考虑最后一行
        if (i == n) {
            for (int j = left; j < i; j++) {
                tmp.append(words[j] + " ");
            }
            tmp.deleteCharAt(tmp.length() - 1);
            for (int j = tmp.length(); j < maxWidth; j++)
                tmp.append(" ");
            res.add(tmp.toString());
            break;
        }
        // 所有单词长度
        int all_word_len = 0;
        for (int j = left; j < i; j++) {
            all_word_len += words[j].length();
        }
        //System.out.println(all_word_len);
        // 至少空格个数
        int space_num = i - left - 1;
        // 可以为空格的位置个数
        int remain_space = maxWidth - all_word_len;
        int a = 0;
        int b = 0;
        if (space_num != 0) {
            a = remain_space / space_num;
            b = remain_space % space_num;
        }
        for (int j = left; j < i; j++) {
            if (tmp.length() > 0) {
                for (int k = 0; k < a; k++) tmp.append(" ");
                if (b != 0) {
                    tmp.append(" ");
                    b--;
                }
            }
            tmp.append(words[j]);
        }
        for (int j = tmp.length(); j < maxWidth; j++) {
            tmp.append(" ");
        }
        res.add(tmp.toString());
    }
    return res;
}

时间复杂度：O(n) 遍历

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github